/*
 * Problem: 01背包问题
 * Author: Yuanshun L
 * Coded: 18-nov-2021
 */

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;


// the problem scale: n <=100, v[i]<=100, w[i]<=100, W<=10000
const int maxn = 100;
const int maxw = 10000;

int n = 4; // the number of thing
int w[maxn] = {2,1,3,2,0}; // weight
int v[maxn] = {3,2,4,2,0}; // value
int W = 5; // the total weight
int dp[maxn+1][maxw+1];

// get the maximum of value from the things after i without excess of j
// ,using the force search algorithm
int force_search(int i,int j){
    if(i == n) // there are nothing to choose
        return 0;
    if(j >= w[i]){ // try two cases
        return max(force_search(i+1,j),force_search(i+1,j-w[i])+v[i]);
    }// the current thing can't be accomdated in the bag
    return force_search(i+1,j);
}

// improve the force search algorithm via introducing memory

int rec(int i,int j){
    if(dp[i][j]>=0)
        return dp[i][j];
    int res;
    if(i==n)
        res = 0;
    else if(j >= w[i]){
        res =  max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
    }
    else{
        res = rec(i+1,j);
    }
    return dp[i][j] = res;
}


// replace the recursion with multiple loops
int rec2(){

    for(int i=n-1;i>=0;i--){
        for(int j=0;j<=W;j++){
            if(j >= w[i]){
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
            }
            else{
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    return dp[0][W];
}

// justify to the forword direction
int rec3(){

    for(int i=0;i<n;i++){
        for(int j=0;j<=W;j++){
            if(j>=w[i])
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            else
                dp[i+1][j] = dp[i][j];
        }
    }
    return dp[n][W];
}



int main(){

    cout << "Force Search Using DBS: " << endl;
    cout << force_search(0,W) << endl;

    memset(dp,-1,sizeof(dp));
    cout << "Dynamic Programming  1 (Recurion): " << endl;
    cout << rec(0,W) << endl;

    memset(dp,0,sizeof(dp));
    cout << "Dynamic Programming  2 (Multilple Loops): " << endl;
    cout << rec2() << endl;

    memset(dp,0,sizeof(dp));
    cout << "Dynamic Programming  3 (Forword Direction): " << endl;
    cout << rec3() <<  endl;

    return 0;
}